/*
题目: 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
https://leetcode.cn/problems/longest-palindromic-substring/
 */
public class LongestPalindrome {
    int n = 0;

    public String longestPalindrome(String s) {
        // 双指针
        n = s.length();
        if (n <= 1)  return s;

        int begin = 0; // 记录结果字符串的起始位置
        int maxLength = 1;
        for (int i = 0; i < n; i++) {
            // 每次以这个奇数, 或者偶数个字母展开
            int lengthOdd = spreadString(s, i, i);
            int lengthEven = spreadString(s, i - 1, i);

            int max = Math.max(lengthOdd, lengthEven);
            if (max > maxLength) {
                begin = i - (max >> 1);
                maxLength = max;
            }
        }

        return s.substring(begin, begin + maxLength);
    }

    // 以某个 / 两个字符展开这个回文串
    private int spreadString(String s, int left ,int right) {
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;
        }
        return right - left - 1;
    }
}
